1. Field of the Invention
This disclosure relates in general to computer applications and more particularly to using rollback RCU with read-side modifications to RCU-protected data structures.
2. Description of Related Art
An operating system kernel is a piece of software responsible for providing secure access from a machine's hardware to various computer programs. The kernel also manages hardware access among a number of programs by deciding when and how long a program should be able to make use of a piece of hardware.
Operating system kernel technologies include read copy-update (RCU) that is used for improving performance on computers with more than one central processing unit (CPU). RCU provides a grace period to concurrent hardware accesses by performing destructive updates in two phases: 1) carrying out enough of each update for new operations to see the new state, while allowing pre-existing operations to proceed on the old state, then 2) completing the update after the grace period expires, so that all pre-existing operations have completed.
There have been a couple of ports of RCU to user-level code, but such straightforward ports are subject to memory exhaustion if one of the processes is preempted indefinitely outside of a quiescent state, which is a thread-execution state during which no references to any RCU-protected data structures are held. Some operating systems permit user processes to suppress preemption, but such suppression is often treated as a hint. Furthermore, not all operating systems provide preemption suppression to user-level processes, with Linux being a prominent case in point. Proposals have been made for having preemption events “roll back” execution to the beginning of an RCU read-side critical section. A critical section is a piece of code that can be executed only by a restricted subset of processes. Critical sections are used to protect against local interrupts and operate on a per-CPU basis, guaranteeing that a thread currently being executed will not be preempted. For read-side critical sections, the region of code is protected from outside interference through some synchronization mechanism, but allows multiple concurrent readers. With regard to “roll back” execution, only read-only read-side critical sections are allowed, making it impossible to use this technique to look up a reference-counted data structure (for example). Note that it is necessary for a preempted thread to be considered to be in a quiescent state in order for RCU to be able to process future RCU callbacks in a timely fashion.
The problem is that the RCU read-side critical section must be idempotent for the proposed “roll back” execution approach to work correctly. If the read-side critical section is not idempotent, deadlock or excess reference counts can occur, resulting in application failure.
It can be seen that there is a need for a restart/rollback process for RCU-protected data structures that avoids deadlock without the requirement of an idempotent read-side critical section.